package leetcode_数组.leetcode_前缀和数组;

/**
 * 这种算数组前缀之类的题目 , 可以看作是动态规划题目 , 因为前缀是用动态规划的思想得出的
 * 区域和 检索 - 数组不可变
 * 最优解就是不要重复遍历数组 , 这样时间就快了
 * 遍历一次得出所需的辅助信息
 */
public class _303 {

    /**
     * 暴力解法
     */
    static class NumArray {
        private int[] nums;

        public NumArray(int[] nums) {
            this.nums = nums;
        }

        public int sumRange(int i, int j) {
            int res = 0;
            for (; i <= j; i++) {
                res += nums[i];
            }
            return res;
        }
    }

    static class NumArray_perfect {
        private int[] prefixSum;

        /**
         * 按照给出的数组，直接计算该数组的前 n 项和
         * 这里给 prefixSum 数组多加了一个元素 , 可以避免在求和的时候多加一个判断
         * 如果不多加一位的话 , 当 i 为 0 的时候 , 返回的是 prefixSum[j]
         * 还有数组为空的时候
         * prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
         *
         * @param nums
         */
        public NumArray_perfect(int[] nums) {
            prefixSum = new int[nums.length + 1];
            prefixSum[0] = 0;
            for (int i = 1; i <= nums.length; i++) {
                prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
            }

        }

        public int sumRange(int i, int j) {
            return prefixSum[j + 1] - prefixSum[i];
        }
    }
}
